/*
337. 打家劫舍 III
https://leetcode.cn/problems/house-robber-iii/description/
困难 2024/12/4
*/

class Solution {
public:
    // 返回一个包含两个元素的向量，分别表示不抢劫和抢劫当前节点时的最大金额
    vector<int> robMoney(TreeNode* node) {
        // 如果节点为空，返回{0, 0}，即不抢劫和抢劫都为0
        if (node == NULL) return {0, 0};

        // 递归计算左子树和右子树的不抢劫和抢劫最大金额
        vector<int> left = robMoney(node->left);
        vector<int> right = robMoney(node->right);

        // 抢劫当前节点，则不能抢劫它的直接子节点
        int robCurr = node->val + left[0] + right[0];

        // 不抢劫当前节点，则可以选择或不抢劫它的直接子节点，取两者中的较大值
        int notRobCurr = max(left[0], left[1]) + max(right[0], right[1]);

        // 返回不抢劫和抢劫当前节点的最大金额
        return {notRobCurr, robCurr};
    }

    // 主函数，计算并返回抢劫该二叉树可以获得的最大金额
    int rob(TreeNode* root) {
        // 计算根节点的不抢劫和抢劫两种情况下的最大金额
        vector<int> result = robMoney(root);

        // 返回两种情况下的最大值
        return max(result[0], result[1]);
    }
};